home *** CD-ROM | disk | FTP | other *** search
/ Apple Developer Connection Student Program / ADC Tools Sampler CD Disk 3 1999.iso / Metrowerks CodeWarrior / Java Support / Java_Source / Java2 / src / java / util / TreeMap.java < prev    next >
Encoding:
Java Source  |  1999-05-28  |  51.4 KB  |  1,618 lines  |  [TEXT/CWIE]
  1. /*
  2.  * @(#)TreeMap.java    1.30 98/09/30
  3.  *
  4.  * Copyright 1997, 1998 by Sun Microsystems, Inc.,
  5.  * 901 San Antonio Road, Palo Alto, California, 94303, U.S.A.
  6.  * All rights reserved.
  7.  *
  8.  * This software is the confidential and proprietary information
  9.  * of Sun Microsystems, Inc. ("Confidential Information").  You
  10.  * shall not disclose such Confidential Information and shall use
  11.  * it only in accordance with the terms of the license agreement
  12.  * you entered into with Sun.
  13.  */
  14.  
  15. package java.util;
  16.  
  17. /**
  18.  * Red-Black tree based implementation of the <tt>SortedMap</tt> interface.
  19.  * This class guarantees that the map will be in ascending key order, sorted
  20.  * according to the <i>natural order</i> for the key's class (see
  21.  * <tt>Comparable</tt>), or by the comparator provided at creation time,
  22.  * depending on which constructor is used.<p>
  23.  *
  24.  * This implementation provides guaranteed log(n) time cost for the
  25.  * <tt>containsKey</tt>, <tt>get</tt>, <tt>put</tt> and <tt>remove</tt>
  26.  * operations.  Algorithms are adaptations of those in Corman, Leiserson, and
  27.  * Rivest's <I>Introduction to Algorithms</I>.<p>
  28.  *
  29.  * Note that the ordering maintained by a sorted map (whether or not an
  30.  * explicit comparator is provided) must be <i>consistent with equals</i> if
  31.  * this sorted map is to correctly implement the <tt>Map</tt> interface.  (See
  32.  * <tt>Comparable</tt> or <tt>Comparator</tt> for a precise definition of
  33.  * <i>consistent with equals</i>.)  This is so because the <tt>Map</tt>
  34.  * interface is defined in terms of the equals operation, but a map performs
  35.  * all key comparisons using its <tt>compareTo</tt> (or <tt>compare</tt>)
  36.  * method, so two keys that are deemed equal by this method are, from the
  37.  * standpoint of the sorted map, equal.  The behavior of a sorted map
  38.  * <i>is</i> well-defined even if its ordering is inconsistent with equals; it
  39.  * just fails to obey the general contract of the <tt>Map</tt> interface.<p>
  40.  *
  41.  * <b>Note that this implementation is not synchronized.</b> If multiple
  42.  * threads access a map concurrently, and at least one of the threads modifies
  43.  * the map structurally, it <i>must</i> be synchronized externally.  (A
  44.  * structural modification is any operation that adds or deletes one or more
  45.  * mappings; merely changing the value associated with an existing key is not
  46.  * a structural modification.)  This is typically accomplished by
  47.  * synchronizing on some object that naturally encapsulates the map.  If no
  48.  * such object exists, the map should be "wrapped" using the
  49.  * <tt>Collections.synchronizedMap</tt> method.  This is best done at creation
  50.  * time, to prevent accidental unsynchronized access to the map: 
  51.  * <pre>
  52.  *     Map m = Collections.synchronizedMap(new TreeMap(...));
  53.  * </pre><p>
  54.  *
  55.  * The iterators returned by all of this class's "collection view methods" are
  56.  * <i>fail-fast</i>: if the map is structurally modified at any time after the
  57.  * iterator is created, in any way except through the iterator's own
  58.  * <tt>remove</tt> or <tt>add</tt> methods, the iterator throws a
  59.  * <tt>ConcurrentModificationException</tt>.  Thus, in the face of concurrent
  60.  * modification, the iterator fails quickly and cleanly, rather than risking
  61.  * arbitrary, non-deterministic behavior at an undetermined time in the
  62.  * future.
  63.  *
  64.  * @author  Josh Bloch and Doug Lea
  65.  * @version 1.30, 09/30/98
  66.  * @see Map
  67.  * @see HashMap
  68.  * @see Hashtable
  69.  * @see Comparable
  70.  * @see Comparator
  71.  * @see Collection
  72.  * @see Collections#synchronizedMap(Map)
  73.  * @since JDK1.2
  74.  */
  75.  
  76. public class TreeMap extends AbstractMap
  77.                  implements SortedMap, Cloneable, java.io.Serializable
  78. {
  79.     /**
  80.      * The Comparator used to maintain order in this TreeMap, or
  81.      * null if this TreeMap uses its elements natural ordering.
  82.      *
  83.      * @serial
  84.      */
  85.     private Comparator comparator = null;
  86.  
  87.     private transient Entry root = null;
  88.  
  89.     /**
  90.      * The number of entries in the tree
  91.      */
  92.     private transient int size = 0;
  93.  
  94.     /**
  95.      * The number of structural modifications to the tree.
  96.      */
  97.     private transient int modCount = 0;
  98.  
  99.     private void incrementSize()   { modCount++; size++; }
  100.     private void decrementSize()   { modCount++; size--; }
  101.  
  102.     /**
  103.      * Constructs a new, empty map, sorted according to the keys' natural
  104.      * order.  All keys inserted into the map must implement the
  105.      * <tt>Comparable</tt> interface.  Furthermore, all such keys must be
  106.      * <i>mutually comparable</i>: <tt>k1.compareTo(k2)</tt> must not throw a
  107.      * ClassCastException for any elements <tt>k1</tt> and <tt>k2</tt> in the
  108.      * map.  If the user attempts to put a key into the map that violates this
  109.      * constraint (for example, the user attempts to put a string key into a
  110.      * map whose keys are integers), the <tt>put(Object key, Object
  111.      * value)</tt> call will throw a <tt>ClassCastException</tt>.
  112.      *
  113.      * @see Comparable
  114.      */
  115.     public TreeMap() {
  116.     }
  117.  
  118.     /**
  119.      * Constructs a new, empty map, sorted according to the given comparator.
  120.      * All keys inserted into the map must be <i>mutually comparable</i> by
  121.      * the given comparator: <tt>comparator.compare(k1, k2)</tt> must not
  122.      * throw a <tt>ClassCastException</tt> for any keys <tt>k1</tt> and
  123.      * <tt>k2</tt> in the map.  If the user attempts to put a key into the
  124.      * map that violates this constraint, the <tt>put(Object key, Object
  125.      * value)</tt> call will throw a <tt>ClassCastException</tt>.
  126.      */
  127.     public TreeMap(Comparator c) {
  128.     this.comparator = c;
  129.     }
  130.  
  131.     /**
  132.      * Constructs a new map containing the same mappings as the given map,
  133.      * sorted according to the keys' <i>natural order</i>.  All keys inserted
  134.      * into the new map must implement the <tt>Comparable</tt> interface.
  135.      * Furthermore, all such keys must be <i>mutually comparable</i>:
  136.      * <tt>k1.compareTo(k2)</tt> must not throw a <tt>ClassCastException</tt>
  137.      * for any elements <tt>k1</tt> and <tt>k2</tt> in the map.  This method
  138.      * runs in n*log(n) time.
  139.      *
  140.      * @throws    ClassCastException the keys in t are not Comparable, or
  141.      * are not mutually comparable.
  142.      */
  143.     public TreeMap(Map m) {
  144.     putAll(m);
  145.     }
  146.  
  147.     /**
  148.      * Constructs a new map containing the same mappings as the given
  149.      * <tt>SortedMap</tt>, sorted according to the same ordering.  This method
  150.      * runs in linear time.
  151.      */
  152.     public TreeMap(SortedMap m) {
  153.         comparator = m.comparator();
  154.         try {
  155.             buildFromSorted(m.size(), m.entrySet().iterator(), null, null);
  156.         } catch (java.io.IOException cannotHappen) {
  157.         } catch (ClassNotFoundException cannotHappen) {
  158.         }
  159.     }
  160.  
  161.  
  162.     // Query Operations
  163.  
  164.     /**
  165.      * Returns the number of key-value mappings in this map.
  166.      *
  167.      * @return the number of key-value mappings in this map.
  168.      */
  169.     public int size() {
  170.     return size;
  171.     }
  172.  
  173.     /**
  174.      * Returns <tt>true</tt> if this map contains a mapping for the specified
  175.      * key.
  176.      *
  177.      * @param key key whose presence in this map is to be tested.
  178.      * 
  179.      * @return <tt>true</tt> if this map contains a mapping for the
  180.      *            specified key.
  181.      * @throws ClassCastException if the key cannot be compared with the keys
  182.      *          currently in the map.
  183.      * @throws NullPointerException key is <tt>null</tt> and this map uses
  184.      *          natural ordering, or its comparator does not tolerate
  185.      *            <tt>null</tt> keys.
  186.      */
  187.     public boolean containsKey(Object key) {
  188.     return getEntry(key) != null;
  189.     }
  190.  
  191.     /**
  192.      * Returns <tt>true</tt> if this map maps one or more keys to the
  193.      * specified value.  More formally, returns <tt>true</tt> if and only if
  194.      * this map contains at least one mapping to a value <tt>v</tt> such
  195.      * that <tt>(value==null ? v==null : value.equals(v))</tt>.  This
  196.      * operation will probably require time linear in the Map size for most
  197.      * implementations of Map.
  198.      *
  199.      * @param value value whose presence in this Map is to be tested.
  200.      * @since JDK1.2
  201.      */
  202.     public boolean containsValue(Object value) {
  203.         return (value==null ? valueSearchNull(root)
  204.                     : valueSearchNonNull(root, value));
  205.     }
  206.  
  207.     private boolean valueSearchNull(Entry n) {
  208.         if (n.value == null)
  209.             return true;
  210.  
  211.         // Check left and right subtrees for value
  212.         return (n.left  != null && valueSearchNull(n.left)) ||
  213.                (n.right != null && valueSearchNull(n.right));
  214.     }
  215.  
  216.     private boolean valueSearchNonNull(Entry n, Object value) {
  217.         // Check this node for the value
  218.         if (value.equals(n.value))
  219.             return true;
  220.  
  221.         // Check left and right subtrees for value
  222.         return (n.left  != null && valueSearchNonNull(n.left, value)) ||
  223.                (n.right != null && valueSearchNonNull(n.right, value));
  224.     }
  225.  
  226.     /**
  227.      * Returns the value to which this map maps the specified key.  Returns
  228.      * <tt>null</tt> if the map contains no mapping for this key.  A return
  229.      * value of <tt>null</tt> does not <i>necessarily</i> indicate that the
  230.      * map contains no mapping for the key; it's also possible that the map
  231.      * explicitly maps the key to <tt>null</tt>.  The <tt>containsKey</tt>
  232.      * operation may be used to distinguish these two cases.
  233.      *
  234.      * @param key key whose associated value is to be returned.
  235.      * @return the value to which this map maps the specified key, or
  236.      *           <tt>null</tt> if the map contains no mapping for the key.
  237.      * @throws    ClassCastException key cannot be compared with the keys
  238.      *          currently in the map.
  239.      * @throws NullPointerException key is <tt>null</tt> and this map uses
  240.      *          natural ordering, or its comparator does not tolerate
  241.      *          <tt>null</tt> keys.
  242.      * 
  243.      * @see #containsKey(Object)
  244.      */
  245.     public Object get(Object key) {
  246.     Entry p = getEntry(key);
  247.     return (p==null ? null : p.value);
  248.     }
  249.  
  250.     /**
  251.      * Returns the comparator used to order this map, or <tt>null</tt> if this
  252.      * map uses its keys' natural order.
  253.      *
  254.      * @return the comparator associated with this sorted map, or
  255.      *            <tt>null</tt> if it uses its keys' natural sort method.
  256.      */
  257.     public Comparator comparator() {
  258.         return comparator;
  259.     }
  260.  
  261.     /**
  262.      * Returns the first (lowest) key currently in this sorted map.
  263.      *
  264.      * @return the first (lowest) key currently in this sorted map.
  265.      * @throws    NoSuchElementException Map is empty.
  266.      */
  267.     public Object firstKey() {
  268.         return key(firstEntry());
  269.     }
  270.  
  271.     /**
  272.      * Returns the last (highest) key currently in this sorted map.
  273.      *
  274.      * @return the last (highest) key currently in this sorted map.
  275.      * @throws    NoSuchElementException Map is empty.
  276.      */
  277.     public Object lastKey() {
  278.         return key(lastEntry());
  279.     }
  280.  
  281.     /**
  282.      * Copies all of the mappings from the specified map to this map.  These
  283.      * mappings replace any mappings that this map had for any of the keys
  284.      * currently in the specified map.
  285.      *
  286.      * @param t Mappings to be stored in this map.
  287.      * @throws    ClassCastException class of a key or value in the specified
  288.      *               map prevents it from being stored in this map.
  289.      * 
  290.      * @throws NullPointerException this map does not permit <tt>null</tt>
  291.      *            keys and a specified key is <tt>null</tt>.
  292.      */
  293.     public void putAll(Map map) {
  294.         int mapSize = map.size();
  295.         if (size==0 && mapSize!=0 && map instanceof SortedMap) {
  296.             Comparator c = ((SortedMap)map).comparator();
  297.             if (c == comparator || (c != null && c.equals(comparator))) {
  298.               ++modCount;
  299.               try {
  300.                   buildFromSorted(mapSize, map.entrySet().iterator(),
  301.                                   null, null);
  302.               } catch (java.io.IOException cannotHappen) {
  303.               } catch (ClassNotFoundException cannotHappen) {
  304.               }
  305.               return;
  306.             }
  307.         }
  308.         super.putAll(map);
  309.     }
  310.  
  311.     /**
  312.      * Returns this map's entry for the given key, or <tt>null</tt> if the map
  313.      * does not contain an entry for the key.
  314.      *
  315.      * @return this map's entry for the given key, or <tt>null</tt> if the map
  316.      *            does not contain an entry for the key.
  317.      * @throws ClassCastException if the key cannot be compared with the keys
  318.      *          currently in the map.
  319.      * @throws NullPointerException key is <tt>null</tt> and this map uses
  320.      *          natural order, or its comparator does not tolerate *
  321.      *          <tt>null</tt> keys.
  322.      */
  323.     private Entry getEntry(Object key) {
  324.     Entry p = root;
  325.     while (p != null) {
  326.         int cmp = compare(key,p.key);
  327.         if (cmp == 0)
  328.         return p;
  329.         else if (cmp < 0)
  330.         p = p.left;
  331.         else
  332.         p = p.right;
  333.     }
  334.     return null;
  335.     }
  336.  
  337.     /**
  338.      * Gets the entry corresponding to the specified key; if no such entry
  339.      * exists, returns the entry for the least key greater than the specified
  340.      * key; if no such entry exists (i.e., the greatest key in the Tree is less
  341.      * than the specified key), returns <tt>null</tt>.
  342.      */
  343.     private Entry getCeilEntry(Object key) {
  344.     Entry p = root;
  345.     if (p==null)
  346.         return null;
  347.  
  348.     while (true) {
  349.         int cmp = compare(key, p.key);
  350.         if (cmp == 0) {
  351.         return p;
  352.         } else if (cmp < 0) {
  353.         if (p.left != null)
  354.             p = p.left;
  355.         else
  356.             return p;
  357.         } else {
  358.         if (p.right != null) {
  359.             p = p.right;
  360.         } else {
  361.             Entry parent = p.parent;
  362.             Entry ch = p;
  363.             while (parent != null && ch == parent.right) {
  364.             ch = parent;
  365.             parent = parent.parent;
  366.             }
  367.             return parent;
  368.         }
  369.         }
  370.     }
  371.     }
  372.  
  373.     /**
  374.      * Returns the entry for the greatest key less than the specified key; if
  375.      * no such entry exists (i.e., the least key in the Tree is greater than
  376.      * the specified key), returns <tt>null</tt>.
  377.      */
  378.     private Entry getPrecedingEntry(Object key) {
  379.     Entry p = root;
  380.     if (p==null)
  381.         return null;
  382.  
  383.     while (true) {
  384.         int cmp = compare(key, p.key);
  385.             if (cmp > 0) {
  386.         if (p.right != null)
  387.             p = p.right;
  388.         else
  389.             return p;
  390.         } else {
  391.         if (p.left != null) {
  392.             p = p.left;
  393.         } else {
  394.             Entry parent = p.parent;
  395.             Entry ch = p;
  396.             while (parent != null && ch == parent.left) {
  397.             ch = parent;
  398.             parent = parent.parent;
  399.             }
  400.             return parent;
  401.         }
  402.         }
  403.     }
  404.     }
  405.  
  406.     /**
  407.      * Returns the key corresonding to the specified Entry.  Throw 
  408.      * NoSuchElementException if the Entry is <tt>null</tt>.
  409.      */
  410.     private static Object key(Entry e) {
  411.         if (e==null)
  412.             throw new NoSuchElementException();
  413.         return e.key;
  414.     }
  415.  
  416.     /**
  417.      * Associates the specified value with the specified key in this map.
  418.      * If the map previously contained a mapping for this key, the old
  419.      * value is replaced.
  420.      *
  421.      * @param key key with which the specified value is to be associated.
  422.      * @param value value to be associated with the specified key.
  423.      * 
  424.      * @return previous value associated with specified key, or <tt>null</tt>
  425.      *           if there was no mapping for key.  A <tt>null</tt> return can
  426.      *           also indicate that the map previously associated <tt>null</tt>
  427.      *           with the specified key.
  428.      * @throws    ClassCastException key cannot be compared with the keys
  429.      *          currently in the map.
  430.      * @throws NullPointerException key is <tt>null</tt> and this map uses
  431.      *          natural order, or its comparator does not tolerate
  432.      *          <tt>null</tt> keys.
  433.      */
  434.     public Object put(Object key, Object value) {
  435.     Entry t = root;
  436.  
  437.     if (t == null) {
  438.         incrementSize();
  439.         root = new Entry(key, value, null);
  440.         return null;
  441.     }
  442.  
  443.     while (true) {
  444.         int cmp = compare(key, t.key);
  445.         if (cmp == 0) {
  446.         return t.setValue(value);
  447.         } else if (cmp < 0) {
  448.         if (t.left != null) {
  449.             t = t.left;
  450.         } else {
  451.             incrementSize();
  452.             t.left = new Entry(key, value, t);
  453.             fixAfterInsertion(t.left);
  454.             return null;
  455.         }
  456.         } else { // cmp > 0
  457.         if (t.right != null) {
  458.             t = t.right;
  459.         } else {
  460.             incrementSize();
  461.             t.right = new Entry(key, value, t);
  462.             fixAfterInsertion(t.right);
  463.             return null;
  464.         }
  465.         }
  466.     }
  467.     }
  468.  
  469.     /**
  470.      * Removes the mapping for this key from this TreeMap if present.
  471.      *
  472.      * @return previous value associated with specified key, or <tt>null</tt>
  473.      *           if there was no mapping for key.  A <tt>null</tt> return can
  474.      *           also indicate that the map previously associated
  475.      *           <tt>null</tt> with the specified key.
  476.      * 
  477.      * @throws    ClassCastException key cannot be compared with the keys
  478.      *          currently in the map.
  479.      * @throws NullPointerException key is <tt>null</tt> and this map uses
  480.      *          natural order, or its comparator does not tolerate
  481.      *          <tt>null</tt> keys.
  482.      */
  483.     public Object remove(Object key) {
  484.     Entry p = getEntry(key);
  485.     if (p == null)
  486.         return null;
  487.  
  488.     Object oldValue = p.value;
  489.     deleteEntry(p);
  490.     return oldValue;
  491.     }
  492.  
  493.     /**
  494.      * Removes all mappings from this TreeMap.
  495.      */
  496.     public void clear() {
  497.     modCount++;
  498.     size = 0;
  499.     root = null;
  500.     }
  501.  
  502.     /**
  503.      * Returns a shallow copy of this <tt>TreeMap</tt> instance. (The keys and
  504.      * values themselves are not cloned.)
  505.      *
  506.      * @return a shallow copy of this Map.
  507.      */
  508.     public Object clone() {
  509.         return new TreeMap(this);
  510.     }
  511.  
  512.  
  513.     // Views
  514.  
  515.     /**
  516.      * These fields are initialized to contain an instance of the appropriate
  517.      * view the first time this view is requested.  The views are stateless,
  518.      * so there's no reason to create more than one of each.
  519.      */
  520.     private transient Set        keySet = null;
  521.     private transient Set        entrySet = null;
  522.     private transient Collection    values = null;
  523.  
  524.     /**
  525.      * Returns a Set view of the keys contained in this map.  The set's
  526.      * iterator will return the keys in ascending order.  The map is backed by
  527.      * this <tt>TreeMap</tt> instance, so changes to this map are reflected in
  528.      * the Set, and vice-versa.  The Set supports element removal, which
  529.      * removes the corresponding mapping from the map, via the
  530.      * <tt>Iterator.remove</tt>, <tt>Set.remove</tt>, <tt>removeAll</tt>,
  531.      * <tt>retainAll</tt>, and <tt>clear</tt> operations.  It does not support
  532.      * the <tt>add</tt> or <tt>addAll</tt> operations.
  533.      *
  534.      * @return a set view of the keys contained in this TreeMap.
  535.      */
  536.     public Set keySet() {
  537.     if (keySet == null) {
  538.         keySet = new AbstractSet() {
  539.         public java.util.Iterator iterator() {
  540.             return new Iterator(KEYS);
  541.         }
  542.  
  543.         public int size() {
  544.             return TreeMap.this.size();
  545.         }
  546.  
  547.                 public boolean contains(Object o) {
  548.                     return containsKey(o);
  549.                 }
  550.  
  551.         public boolean remove(Object o) {
  552.             return TreeMap.this.remove(o) != null;
  553.         }
  554.  
  555.         public void clear() {
  556.             TreeMap.this.clear();
  557.         }
  558.         };
  559.     }
  560.     return keySet;
  561.     }
  562.  
  563.     /**
  564.      * Returns a collection view of the values contained in this map.  The
  565.      * collection's iterator will return the values in the order that their
  566.      * corresponding keys appear in the tree.  The collection is backed by
  567.      * this <tt>TreeMap</tt> instance, so changes to this map are reflected in
  568.      * the collection, and vice-versa.  The collection supports element
  569.      * removal, which removes the corresponding mapping from the map through
  570.      * the <tt>Iterator.remove</tt>, <tt>Collection.remove</tt>,
  571.      * <tt>removeAll</tt>, <tt>retainAll</tt>, and <tt>clear</tt> operations.
  572.      * It does not support the <tt>add</tt> or <tt>addAll</tt> operations.
  573.      *
  574.      * @return a collection view of the values contained in this map.
  575.      */
  576.     public Collection values() {
  577.     if (values == null) {
  578.             values = new AbstractCollection() {
  579.                 public java.util.Iterator iterator() {
  580.                     return new Iterator(VALUES);
  581.                 }
  582.  
  583.                 public int size() {
  584.                     return TreeMap.this.size();
  585.                 }
  586.  
  587.                 public boolean contains(Object o) {
  588.                     for (Entry e = firstEntry(); e != null; e = successor(e))
  589.                         if (valEquals(e.getValue(), o))
  590.                             return true;
  591.                     return false;
  592.                 }
  593.  
  594.         public boolean remove(Object o) {
  595.                     for (Entry e = firstEntry(); e != null; e = successor(e)) {
  596.                         if (valEquals(e.getValue(), o)) {
  597.                             deleteEntry(e);
  598.                             return true;
  599.                         }
  600.                     }
  601.                     return false;
  602.         }
  603.  
  604.                 public void clear() {
  605.                     TreeMap.this.clear();
  606.                 }
  607.             };
  608.         }
  609.         return values;
  610.     }
  611.  
  612.     /**
  613.      * Returns a set view of the mappings contained in this map.  The set's
  614.      * iterator returns the mappings in ascending key order.  Each element in
  615.      * the returned set is a <tt>Map.Entry</tt>.  The set is backed by this
  616.      * map, so changes to this map are reflected in the set, and vice-versa.
  617.      * The set supports element removal, which removes the corresponding
  618.      * mapping from the TreeMap, through the <tt>Iterator.remove</tt>,
  619.      * <tt>Set.remove</tt>, <tt>removeAll</tt>, <tt>retainAll</tt> and
  620.      * <tt>clear</tt> operations.  It does not support the <tt>add</tt> or
  621.      * <tt>addAll</tt> operations.
  622.      *
  623.      * @return a set view of the mappings contained in this map.
  624.      * @see Map.Entry
  625.      */
  626.     public Set entrySet() {
  627.     if (entrySet == null) {
  628.         entrySet = new AbstractSet() {
  629.                 public java.util.Iterator iterator() {
  630.                     return new Iterator(ENTRIES);
  631.                 }
  632.  
  633.                 public boolean contains(Object o) {
  634.                     if (!(o instanceof Map.Entry))
  635.                         return false;
  636.                     Map.Entry entry = (Map.Entry)o;
  637.                     Object value = entry.getValue();
  638.                     Entry p = getEntry(entry.getKey());
  639.                     return p != null && valEquals(p.getValue(), value);
  640.                 }
  641.  
  642.         public boolean remove(Object o) {
  643.                     if (!(o instanceof Map.Entry))
  644.                         return false;
  645.                     Map.Entry entry = (Map.Entry)o;
  646.                     Object value = entry.getValue();
  647.                     Entry p = getEntry(entry.getKey());
  648.                     if (p != null && valEquals(p.getValue(), value)) {
  649.                         deleteEntry(p);
  650.                         return true;
  651.                     }
  652.                     return false;
  653.                 }
  654.  
  655.                 public int size() {
  656.                     return TreeMap.this.size();
  657.                 }
  658.  
  659.                 public void clear() {
  660.                     TreeMap.this.clear();
  661.                 }
  662.             };
  663.         }
  664.     return entrySet;
  665.     }
  666.  
  667.     /**
  668.      * Returns a view of the portion of this map whose keys range from
  669.      * <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive.  (If
  670.      * <tt>fromKey</tt> and <tt>toKey</tt> are equal, the returned sorted map
  671.      * is empty.)  The returned sorted map is backed by this map, so changes
  672.      * in the returned sorted map are reflected in this map, and vice-versa.
  673.      * The returned sorted map supports all optional map operations.<p>
  674.      *
  675.      * The sorted map returned by this method will throw an
  676.      * <tt>IllegalArgumentException</tt> if the user attempts to insert a key
  677.      * less than <tt>fromKey</tt> or greater than or equal to
  678.      * <tt>toKey</tt>.<p>
  679.      *
  680.      * Note: this method always returns a <i>half-open range</i> (which
  681.      * includes its low endpoint but not its high endpoint).  If you need a
  682.      * <i>closed range</i> (which includes both endpoints), and the key type
  683.      * allows for calculation of the successor a given key, merely request the
  684.      * subrange from <tt>lowEndpoint</tt> to <tt>successor(highEndpoint)</tt>.
  685.      * For example, suppose that <tt>m</tt> is a sorted map whose keys are
  686.      * strings.  The following idiom obtains a view containing all of the
  687.      * key-value mappings in <tt>m</tt> whose keys are between <tt>low</tt>
  688.      * and <tt>high</tt>, inclusive:
  689.      *         <pre>    SortedMap sub = m.submap(low, high+"\0");</pre>
  690.      * A similar technique can be used to generate an <i>open range</i> (which
  691.      * contains neither endpoint).  The following idiom obtains a view
  692.      * containing all of the key-value mappings in <tt>m</tt> whose keys are
  693.      * between <tt>low</tt> and <tt>high</tt>, exclusive:
  694.      *         <pre>    SortedMap sub = m.subMap(low+"\0", high);</pre>
  695.      *
  696.      * @param fromKey low endpoint (inclusive) of the subMap.
  697.      * @param toKey high endpoint (exclusive) of the subMap.
  698.      * 
  699.      * @return a view of the portion of this map whose keys range from
  700.      *            <tt>fromKey</tt>, inclusive, to <tt>toKey</tt>, exclusive.
  701.      * 
  702.      * @throws NullPointerException if <tt>fromKey</tt> or <tt>toKey</tt> is
  703.      *          <tt>null</tt> and this map uses natural order, or its
  704.      *          comparator does not tolerate <tt>null</tt> keys.
  705.      * 
  706.      * @throws IllegalArgumentException if <tt>fromKey</tt> is greater than
  707.      *            <tt>toKey</tt>.
  708.      */
  709.     public SortedMap subMap(Object fromKey, Object toKey) {
  710.     return new SubMap(fromKey, toKey);
  711.     }
  712.  
  713.     /**
  714.      * Returns a view of the portion of this map whose keys are strictly less
  715.      * than <tt>toKey</tt>.  The returned sorted map is backed by this map, so
  716.      * changes in the returned sorted map are reflected in this map, and
  717.      * vice-versa.  The returned sorted map supports all optional map
  718.      * operations.<p>
  719.      *
  720.      * The sorted map returned by this method will throw an
  721.      * <tt>IllegalArgumentException</tt> if the user attempts to insert a key
  722.      * greater than or equal to <tt>toKey</tt>.<p>
  723.      *
  724.      * Note: this method always returns a view that does not contain its
  725.      * (high) endpoint.  If you need a view that does contain this endpoint,
  726.      * and the key type allows for calculation of the successor a given key,
  727.      * merely request a headMap bounded by <tt>successor(highEndpoint)</tt>.
  728.      * For example, suppose that suppose that <tt>m</tt> is a sorted map whose
  729.      * keys are strings.  The following idiom obtains a view containing all of
  730.      * the key-value mappings in <tt>m</tt> whose keys are less than or equal
  731.      * to <tt>high</tt>:
  732.      * <pre>
  733.      *     SortedMap head = m.headMap(high+"\0");
  734.      * </pre>
  735.      *
  736.      * @param toKey high endpoint (exclusive) of the headMap.
  737.      * @return a view of the portion of this map whose keys are strictly
  738.      *            less than <tt>toKey</tt>.
  739.      * @throws NullPointerException if <tt>toKey</tt> is <tt>null</tt> and
  740.      *          this map uses natural order, or its comparator does * not
  741.      *          tolerate <tt>null</tt> keys.
  742.      */
  743.     public SortedMap headMap(Object toKey) {
  744.     return new SubMap(toKey, true);
  745.     }
  746.  
  747.     /**
  748.      * Returns a view of the portion of this map whose keys are greater than
  749.      * or equal to <tt>fromKey</tt>.  The returned sorted map is backed by
  750.      * this map, so changes in the returned sorted map are reflected in this
  751.      * map, and vice-versa.  The returned sorted map supports all optional map
  752.      * operations.<p>
  753.      *
  754.      * The sorted map returned by this method will throw an
  755.      * <tt>IllegalArgumentException</tt> if the user attempts to insert a key
  756.      * less than <tt>fromKey</tt>.<p>
  757.      *
  758.      * Note: this method always returns a view that contains its (low)
  759.      * endpoint.  If you need a view that does not contain this endpoint, and
  760.      * the element type allows for calculation of the successor a given value,
  761.      * merely request a tailMap bounded by <tt>successor(lowEndpoint)</tt>.
  762.      * For For example, suppose that suppose that <tt>m</tt> is a sorted map
  763.      * whose keys are strings.  The following idiom obtains a view containing
  764.      * all of the key-value mappings in <tt>m</tt> whose keys are strictly
  765.      * greater than <tt>low</tt>: <pre>
  766.      *     SortedMap tail = m.tailMap(low+"\0");
  767.      * </pre>
  768.      *
  769.      * @param fromKey low endpoint (inclusive) of the tailMap.
  770.      * @return a view of the portion of this map whose keys are greater
  771.      *            than or equal to <tt>fromKey</tt>.
  772.      * @throws    NullPointerException fromKey is <tt>null</tt> and this
  773.      *          map uses natural ordering, or its comparator does
  774.      *            not tolerate <tt>null</tt> keys.
  775.      */
  776.     public SortedMap tailMap(Object fromKey) {
  777.     return new SubMap(fromKey, false);
  778.     }
  779.  
  780.     private class SubMap extends AbstractMap
  781.                  implements SortedMap, java.io.Serializable {
  782.         /**
  783.          * fromKey is significant only if fromStart is false.  Similarly,
  784.          * toKey is significant only if toStart is false.
  785.          */
  786.         private boolean fromStart = false, toEnd = false;
  787.     private Object  fromKey,           toKey;
  788.  
  789.     SubMap(Object fromKey, Object toKey) {
  790.         if (compare(fromKey, toKey) > 0)
  791.         throw new IllegalArgumentException("fromKey > toKey");
  792.         this.fromKey = fromKey;
  793.         this.toKey = toKey;
  794.     }
  795.  
  796.     SubMap(Object key, boolean headMap) {
  797.             if (headMap) {
  798.                 fromStart = true;
  799.                 toKey = key;
  800.             } else {
  801.                 toEnd = true;
  802.                 fromKey = key;
  803.             }
  804.     }
  805.  
  806.     SubMap(boolean fromStart, Object fromKey, boolean toEnd, Object toKey){
  807.             this.fromStart = fromStart;
  808.             this.fromKey= fromKey;
  809.             this.toEnd = toEnd;
  810.             this.toKey = toKey;
  811.     }
  812.  
  813.     public boolean isEmpty() {
  814.         return entrySet.isEmpty();
  815.     }
  816.  
  817.     public boolean containsKey(Object key) {
  818.         return inRange(key) && TreeMap.this.containsKey(key);
  819.     }
  820.  
  821.     public Object get(Object key) {
  822.         if (!inRange(key))
  823.                 return null;
  824.         return TreeMap.this.get(key);
  825.     }
  826.  
  827.     public Object put(Object key, Object value) {
  828.         if (!inRange(key))
  829.         throw new IllegalArgumentException("key out of range");
  830.         return TreeMap.this.put(key, value);
  831.     }
  832.  
  833.         public Comparator comparator() {
  834.             return comparator;
  835.         }
  836.  
  837.         public Object firstKey() {
  838.             return key(fromStart ? firstEntry() : getCeilEntry(fromKey));
  839.         }
  840.  
  841.         public Object lastKey() {
  842.             return key(toEnd ? lastEntry() : getPrecedingEntry(toKey));
  843.         }
  844.  
  845.     private transient Set entrySet = new EntrySetView();
  846.  
  847.     public Set entrySet() {
  848.         return entrySet;
  849.     }
  850.  
  851.     private class EntrySetView extends AbstractSet {
  852.         private transient int size = -1, sizeModCount;
  853.  
  854.         public int size() {
  855.         if (size == -1 || sizeModCount != TreeMap.this.modCount) {
  856.             size = 0;  sizeModCount = TreeMap.this.modCount;
  857.             java.util.Iterator i = iterator();
  858.             while (i.hasNext()) {
  859.             size++;
  860.             i.next();
  861.             }
  862.         }
  863.         return size;
  864.         }
  865.  
  866.         public boolean isEmpty() {
  867.         return !iterator().hasNext();
  868.         }
  869.  
  870.         public boolean contains(Object o) {
  871.         if (!(o instanceof Map.Entry))
  872.             return false;
  873.         Map.Entry entry = (Map.Entry)o;
  874.         Object key = entry.getKey();
  875.                 if (!inRange(key))
  876.                     return false;
  877.                 Entry node = getEntry(key);
  878.                 return node != null &&
  879.                        valEquals(node.getValue(), entry.getValue());
  880.         }
  881.  
  882.         public boolean remove(Object o) {
  883.         if (!(o instanceof Map.Entry))
  884.             return false;
  885.         Map.Entry entry = (Map.Entry)o;
  886.         Object key = entry.getKey();
  887.                 if (!inRange(key))
  888.                     return false;
  889.                 Entry node = getEntry(key);
  890.                 if (node!=null && valEquals(node.getValue(),entry.getValue())){
  891.             deleteEntry(node);
  892.             return true;
  893.                 }
  894.                 return false;
  895.         }
  896.  
  897.         public java.util.Iterator iterator() {
  898.         return new Iterator(
  899.                     (fromStart ? firstEntry() : getCeilEntry(fromKey)),
  900.                     (toEnd     ? null          : getCeilEntry(toKey)));
  901.         }
  902.     }
  903.  
  904.         public SortedMap subMap(Object fromKey, Object toKey) {
  905.             if (!inRange(fromKey))
  906.         throw new IllegalArgumentException("fromKey out of range");
  907.             if (!inRange2(toKey))
  908.                 throw new IllegalArgumentException("toKey out of range");
  909.             return new SubMap(fromKey, toKey);
  910.         }
  911.  
  912.         public SortedMap headMap(Object toKey) {
  913.             if (!inRange2(toKey))
  914.                 throw new IllegalArgumentException("toKey out of range");
  915.             return new SubMap(fromStart, fromKey, false, toKey);
  916.         }
  917.  
  918.         public SortedMap tailMap(Object fromKey) {
  919.             if (!inRange(fromKey))
  920.                 throw new IllegalArgumentException("fromKey out of range");
  921.             return new SubMap(false, fromKey, toEnd, toKey);
  922.         }
  923.  
  924.     private boolean inRange(Object key) {
  925.         return (fromStart || compare(key, fromKey) >= 0) &&
  926.                    (toEnd     || compare(key, toKey)   <  0);
  927.     }
  928.  
  929.         // This form allows the high endpoint (as well as all legit keys)
  930.     private boolean inRange2(Object key) {
  931.         return (fromStart || compare(key, fromKey) >= 0) &&
  932.                    (toEnd     || compare(key, toKey)   <= 0);
  933.         }
  934.     }
  935.  
  936.     // Types of Iterators
  937.     private static final int KEYS = 0;
  938.     private static final int VALUES = 1;
  939.     private static final int ENTRIES = 2;
  940.  
  941.     /**
  942.      * TreeMap Iterator.
  943.      */
  944.     private class Iterator implements java.util.Iterator {
  945.     private int type;
  946.     private int expectedModCount = TreeMap.this.modCount;
  947.     private Entry lastReturned = null;
  948.     private Entry next;
  949.     private Entry firstExcluded = null;
  950.  
  951.     Iterator(int type) {
  952.         this.type = type;
  953.         next = firstEntry();
  954.     }
  955.  
  956.     Iterator(Entry first, Entry firstExcluded) {
  957.         type = ENTRIES;
  958.         next = first;
  959.         this.firstExcluded = firstExcluded;
  960.     }
  961.  
  962.     public boolean hasNext() {
  963.         return next != firstExcluded;
  964.     }
  965.  
  966.     public Object next() {
  967.         if (next == firstExcluded)
  968.         throw new NoSuchElementException();
  969.         if (modCount != expectedModCount)
  970.         throw new ConcurrentModificationException();
  971.  
  972.         lastReturned = next;
  973.         next = successor(next);
  974.         return (type == KEYS ? lastReturned.key :
  975.             (type == VALUES ? lastReturned.value : lastReturned));
  976.     }
  977.  
  978.     public void remove() {
  979.         if (lastReturned == null)
  980.         throw new IllegalStateException();
  981.         if (modCount != expectedModCount)
  982.         throw new ConcurrentModificationException();
  983.  
  984.         deleteEntry(lastReturned);
  985.         expectedModCount++;
  986.         lastReturned = null;
  987.     }
  988.     }
  989.  
  990.     /**
  991.      * Compares two keys using the correct comparison method for this TreeMap.
  992.      */
  993.     private int compare(Object k1, Object k2) {
  994.     return (comparator==null ? ((Comparable)k1).compareTo(k2)
  995.                  : comparator.compare(k1, k2));
  996.     }
  997.  
  998.     /**
  999.      * Test two values  for equality.  Differs from o1.equals(o2) only in
  1000.      * that it copes with with <tt>null</tt> o1 properly.
  1001.      */
  1002.     private static boolean valEquals(Object o1, Object o2) {
  1003.         return (o1==null ? o2==null : o1.equals(o2));
  1004.     }
  1005.  
  1006.     private static final boolean RED   = false;
  1007.     private static final boolean BLACK = true;
  1008.  
  1009.     /**
  1010.      * Node in the Tree.  Doubles as a means to pass key-value pairs back to
  1011.      * user (see Map.Entry).
  1012.      */
  1013.  
  1014.     static class Entry implements Map.Entry {
  1015.     Object key;
  1016.     Object value;
  1017.     Entry left = null;
  1018.     Entry right = null;
  1019.     Entry parent;
  1020.     boolean color = BLACK;
  1021.  
  1022.     /**
  1023.      * Make a new cell with given key, value, and parent, and with <tt>null</tt>
  1024.      * child links, and BLACK color. 
  1025.      */
  1026.     Entry(Object key, Object value, Entry parent) { 
  1027.         this.key = key;
  1028.         this.value = value;
  1029.         this.parent = parent;
  1030.     }
  1031.  
  1032.     /**
  1033.      * Returns the key.
  1034.          *
  1035.      * @return the key.
  1036.      */
  1037.     public Object getKey() { 
  1038.         return key; 
  1039.     }
  1040.  
  1041.     /**
  1042.      * Returns the value associated with the key.
  1043.          *
  1044.      * @return the value associated with the key.
  1045.      */
  1046.     public Object getValue() {
  1047.         return value;
  1048.     }
  1049.  
  1050.     /**
  1051.      * Replaces the value currently associated with the key with the given
  1052.      * value.
  1053.          *
  1054.          * @return the value associated with the key before this method was
  1055.          *       called.
  1056.      */
  1057.     public Object setValue(Object value) {
  1058.         Object oldValue = this.value;
  1059.         this.value = value;
  1060.         return oldValue;
  1061.     }
  1062.  
  1063.     public boolean equals(Object o) {
  1064.         if (!(o instanceof Map.Entry))
  1065.         return false;
  1066.         Map.Entry e = (Map.Entry)o;
  1067.  
  1068.         return valEquals(key,e.getKey()) && valEquals(value,e.getValue());
  1069.     }
  1070.  
  1071.     public int hashCode() {
  1072.         int keyHash = (key==null ? 0 : key.hashCode());
  1073.         int valueHash = (value==null ? 0 : value.hashCode());
  1074.         return keyHash ^ valueHash;
  1075.     }
  1076.  
  1077.     public String toString() {
  1078.         return key + "=" + value;
  1079.     }
  1080.     }
  1081.  
  1082.     /**
  1083.      * Returns the first Entry in the TreeMap (according to the TreeMap's
  1084.      * key-sort function).  Returns null if the TreeMap is empty.
  1085.      */
  1086.     private Entry firstEntry() {
  1087.     Entry p = root;
  1088.     if (p != null)
  1089.         while (p.left != null)
  1090.         p = p.left;
  1091.     return p;
  1092.     }
  1093.  
  1094.     /**
  1095.      * Returns the last Entry in the TreeMap (according to the TreeMap's
  1096.      * key-sort function).  Returns null if the TreeMap is empty.
  1097.      */
  1098.     private Entry lastEntry() {
  1099.     Entry p = root;
  1100.     if (p != null)
  1101.         while (p.right != null)
  1102.         p = p.right;
  1103.     return p;
  1104.     }
  1105.  
  1106.     /**
  1107.      * Returns the successor of the specified Entry, or null if no such.
  1108.      */
  1109.     private Entry successor(Entry t) {
  1110.     if (t == null)
  1111.         return null;
  1112.     else if (t.right != null) {
  1113.         Entry p = t.right;
  1114.         while (p.left != null)
  1115.         p = p.left;
  1116.         return p;
  1117.     } else {
  1118.         Entry p = t.parent;
  1119.         Entry ch = t;
  1120.         while (p != null && ch == p.right) {
  1121.         ch = p;
  1122.         p = p.parent;
  1123.         }
  1124.         return p;
  1125.     }
  1126.     }
  1127.  
  1128.     /**
  1129.      * Balancing operations.
  1130.      *
  1131.      * Implementations of rebalancings during insertion and deletion are
  1132.      * slightly different than the CLR version.  Rather than using dummy
  1133.      * nilnodes, we use a set of accessors that deal properly with null.  They
  1134.      * are used to avoid messiness surrounding nullness checks in the main
  1135.      * algorithms.
  1136.      */
  1137.  
  1138.     private static boolean colorOf(Entry p) {
  1139.     return (p == null ? BLACK : p.color);
  1140.     }
  1141.  
  1142.     private static Entry  parentOf(Entry p) { 
  1143.     return (p == null ? null: p.parent);
  1144.     }
  1145.  
  1146.     private static void setColor(Entry p, boolean c) { 
  1147.     if (p != null)  p.color = c; 
  1148.     }
  1149.  
  1150.     private static Entry  leftOf(Entry p) { 
  1151.     return (p == null)? null: p.left; 
  1152.     }
  1153.  
  1154.     private static Entry  rightOf(Entry p) { 
  1155.     return (p == null)? null: p.right; 
  1156.     }
  1157.  
  1158.     /** From CLR **/
  1159.     private void rotateLeft(Entry p) {
  1160.     Entry r = p.right;
  1161.     p.right = r.left;
  1162.     if (r.left != null)
  1163.         r.left.parent = p;
  1164.     r.parent = p.parent;
  1165.     if (p.parent == null)
  1166.         root = r;
  1167.     else if (p.parent.left == p)
  1168.         p.parent.left = r;
  1169.     else
  1170.         p.parent.right = r;
  1171.     r.left = p;
  1172.     p.parent = r;
  1173.     }
  1174.  
  1175.     /** From CLR **/
  1176.     private void rotateRight(Entry p) {
  1177.     Entry l = p.left;
  1178.     p.left = l.right;
  1179.     if (l.right != null) l.right.parent = p;
  1180.     l.parent = p.parent;
  1181.     if (p.parent == null)
  1182.         root = l;
  1183.     else if (p.parent.right == p)
  1184.         p.parent.right = l;
  1185.     else p.parent.left = l;
  1186.     l.right = p;
  1187.     p.parent = l;
  1188.     }
  1189.  
  1190.  
  1191.     /** From CLR **/
  1192.     private void fixAfterInsertion(Entry x) {
  1193.     x.color = RED;
  1194.  
  1195.     while (x != null && x != root && x.parent.color == RED) {
  1196.         if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
  1197.         Entry y = rightOf(parentOf(parentOf(x)));
  1198.         if (colorOf(y) == RED) {
  1199.             setColor(parentOf(x), BLACK);
  1200.             setColor(y, BLACK);
  1201.             setColor(parentOf(parentOf(x)), RED);
  1202.             x = parentOf(parentOf(x));
  1203.         } else {
  1204.             if (x == rightOf(parentOf(x))) {
  1205.             x = parentOf(x);
  1206.             rotateLeft(x);
  1207.             }
  1208.             setColor(parentOf(x), BLACK);
  1209.             setColor(parentOf(parentOf(x)), RED);
  1210.             if (parentOf(parentOf(x)) != null) 
  1211.             rotateRight(parentOf(parentOf(x)));
  1212.         }
  1213.         } else {
  1214.         Entry y = leftOf(parentOf(parentOf(x)));
  1215.         if (colorOf(y) == RED) {
  1216.             setColor(parentOf(x), BLACK);
  1217.             setColor(y, BLACK);
  1218.             setColor(parentOf(parentOf(x)), RED);
  1219.             x = parentOf(parentOf(x));
  1220.         } else {
  1221.             if (x == leftOf(parentOf(x))) {
  1222.             x = parentOf(x);
  1223.             rotateRight(x);
  1224.             }
  1225.             setColor(parentOf(x),  BLACK);
  1226.             setColor(parentOf(parentOf(x)), RED);
  1227.             if (parentOf(parentOf(x)) != null) 
  1228.             rotateLeft(parentOf(parentOf(x)));
  1229.         }
  1230.         }
  1231.     }
  1232.     root.color = BLACK;
  1233.     }
  1234.  
  1235.     /**
  1236.      * Delete node p, and then rebalance the tree.
  1237.      */
  1238.     private void deleteEntry(Entry p) {
  1239.         decrementSize();
  1240.  
  1241.     // If strictly internal, first swap position with successor.
  1242.     if (p.left != null && p.right != null) {
  1243.         Entry s = successor(p);
  1244.         swapPosition(s, p);
  1245.     } 
  1246.  
  1247.     // Start fixup at replacement node, if it exists.
  1248.     Entry replacement = (p.left != null ? p.left : p.right);
  1249.  
  1250.     if (replacement != null) {
  1251.         // Link replacement to parent 
  1252.         replacement.parent = p.parent;
  1253.         if (p.parent == null)       
  1254.         root = replacement; 
  1255.         else if (p == p.parent.left)  
  1256.         p.parent.left  = replacement;
  1257.         else
  1258.         p.parent.right = replacement;
  1259.  
  1260.         // Null out links so they are OK to use by fixAfterDeletion.
  1261.         p.left = p.right = p.parent = null;
  1262.       
  1263.         // Fix replacement
  1264.         if (p.color == BLACK) 
  1265.         fixAfterDeletion(replacement);
  1266.     } else if (p.parent == null) { // return if we are the only node.
  1267.         root = null;
  1268.     } else { //  No children. Use self as phantom replacement and unlink.
  1269.         if (p.color == BLACK) 
  1270.         fixAfterDeletion(p);
  1271.  
  1272.         if (p.parent != null) {
  1273.         if (p == p.parent.left) 
  1274.             p.parent.left = null;
  1275.         else if (p == p.parent.right) 
  1276.             p.parent.right = null;
  1277.         p.parent = null;
  1278.         }
  1279.     }
  1280.     }
  1281.  
  1282.     /** From CLR **/
  1283.     private void fixAfterDeletion(Entry x) {
  1284.     while (x != root && colorOf(x) == BLACK) {
  1285.         if (x == leftOf(parentOf(x))) {
  1286.         Entry sib = rightOf(parentOf(x));
  1287.  
  1288.         if (colorOf(sib) == RED) {
  1289.             setColor(sib, BLACK);
  1290.             setColor(parentOf(x), RED);
  1291.             rotateLeft(parentOf(x));
  1292.             sib = rightOf(parentOf(x));
  1293.         }
  1294.  
  1295.         if (colorOf(leftOf(sib))  == BLACK && 
  1296.             colorOf(rightOf(sib)) == BLACK) {
  1297.             setColor(sib,  RED);
  1298.             x = parentOf(x);
  1299.         } else {
  1300.             if (colorOf(rightOf(sib)) == BLACK) {
  1301.             setColor(leftOf(sib), BLACK);
  1302.             setColor(sib, RED);
  1303.             rotateRight(sib);
  1304.             sib = rightOf(parentOf(x));
  1305.             }
  1306.             setColor(sib, colorOf(parentOf(x)));
  1307.             setColor(parentOf(x), BLACK);
  1308.             setColor(rightOf(sib), BLACK);
  1309.             rotateLeft(parentOf(x));
  1310.             x = root;
  1311.         }
  1312.         } else { // symmetric
  1313.         Entry sib = leftOf(parentOf(x));
  1314.  
  1315.         if (colorOf(sib) == RED) {
  1316.             setColor(sib, BLACK);
  1317.             setColor(parentOf(x), RED);
  1318.             rotateRight(parentOf(x));
  1319.             sib = leftOf(parentOf(x));
  1320.         }
  1321.  
  1322.         if (colorOf(rightOf(sib)) == BLACK && 
  1323.             colorOf(leftOf(sib)) == BLACK) {
  1324.             setColor(sib,  RED);
  1325.             x = parentOf(x);
  1326.         } else {
  1327.             if (colorOf(leftOf(sib)) == BLACK) {
  1328.             setColor(rightOf(sib), BLACK);
  1329.             setColor(sib, RED);
  1330.             rotateLeft(sib);
  1331.             sib = leftOf(parentOf(x));
  1332.             }
  1333.             setColor(sib, colorOf(parentOf(x)));
  1334.             setColor(parentOf(x), BLACK);
  1335.             setColor(leftOf(sib), BLACK);
  1336.             rotateRight(parentOf(x));
  1337.             x = root;
  1338.         }
  1339.         }
  1340.     }
  1341.  
  1342.     setColor(x, BLACK); 
  1343.     }
  1344.  
  1345.     /**
  1346.      * Swap the linkages of two nodes in a tree.
  1347.      */
  1348.     private void swapPosition(Entry x, Entry y) {
  1349.     // Save initial values.
  1350.     Entry px = x.parent, lx = x.left, rx = x.right;
  1351.     Entry py = y.parent, ly = y.left, ry = y.right;
  1352.     boolean xWasLeftChild = px != null && x == px.left;
  1353.     boolean yWasLeftChild = py != null && y == py.left;
  1354.  
  1355.     // Swap, handling special cases of one being the other's parent.
  1356.     if (x == py) {  // x was y's parent
  1357.         x.parent = y;
  1358.         if (yWasLeftChild) { 
  1359.         y.left = x; 
  1360.         y.right = rx; 
  1361.         } else {
  1362.         y.right = x;
  1363.         y.left = lx;  
  1364.         }
  1365.     } else {
  1366.         x.parent = py; 
  1367.         if (py != null) {
  1368.         if (yWasLeftChild)
  1369.             py.left = x;
  1370.         else
  1371.             py.right = x;
  1372.         }
  1373.         y.left = lx;   
  1374.         y.right = rx;
  1375.     }
  1376.  
  1377.     if (y == px) { // y was x's parent
  1378.         y.parent = x;
  1379.         if (xWasLeftChild) { 
  1380.         x.left = y; 
  1381.         x.right = ry; 
  1382.         } else {
  1383.         x.right = y;
  1384.         x.left = ly;  
  1385.         }
  1386.     } else {
  1387.         y.parent = px; 
  1388.         if (px != null) {
  1389.         if (xWasLeftChild)
  1390.             px.left = y;
  1391.         else
  1392.             px.right = y;
  1393.         }
  1394.         x.left = ly;   
  1395.         x.right = ry;  
  1396.     }
  1397.  
  1398.     // Fix children's parent pointers
  1399.     if (x.left != null)
  1400.         x.left.parent = x;
  1401.     if (x.right != null)
  1402.         x.right.parent = x;
  1403.     if (y.left != null)
  1404.         y.left.parent = y;
  1405.     if (y.right != null)
  1406.         y.right.parent = y;
  1407.  
  1408.     // Swap colors
  1409.     boolean c = x.color;
  1410.     x.color = y.color;
  1411.     y.color = c;
  1412.  
  1413.     // Check if root changed
  1414.     if (root == x)
  1415.         root = y;
  1416.     else if (root == y)
  1417.         root = x;
  1418.     }
  1419.  
  1420.  
  1421.  
  1422.  
  1423.     /**
  1424.      * Save the state of the <tt>TreeMap</tt> instance to a stream (i.e.,
  1425.      * serialize it).
  1426.      *
  1427.      * @serialData The <i>size</i> of the TreeMap (the number of key-value
  1428.      *           mappings) is emitted (int), followed by the key (Object)
  1429.      *           and value (Object) for each key-value mapping represented
  1430.      *           by the TreeMap. The key-value mappings are emitted in
  1431.      *           key-order (as determined by the TreeMap's Comparator,
  1432.      *           or by the keys' natural ordering if the TreeMap has no
  1433.      *             Comparator).
  1434.      */
  1435.     private void writeObject(java.io.ObjectOutputStream s)
  1436.         throws java.io.IOException {
  1437.     // Write out the Comparator and any hidden stuff
  1438.     s.defaultWriteObject();
  1439.  
  1440.     // Write out size (number of Mappings)
  1441.     s.writeInt(size);
  1442.  
  1443.         // Write out keys and values (alternating)
  1444.     for (java.util.Iterator i = entrySet().iterator(); i.hasNext(); ) {
  1445.             Entry e = (Entry)i.next();
  1446.             s.writeObject(e.key);
  1447.             s.writeObject(e.value);
  1448.     }
  1449.     }
  1450.  
  1451.  
  1452.  
  1453.     /**
  1454.      * Reconstitute the <tt>TreeMap</tt> instance from a stream (i.e.,
  1455.      * deserialize it).
  1456.      */
  1457.     private void readObject(final java.io.ObjectInputStream s)
  1458.         throws java.io.IOException, ClassNotFoundException {
  1459.     // Read in the Comparator and any hidden stuff
  1460.     s.defaultReadObject();
  1461.  
  1462.         // Read in size
  1463.         int size = s.readInt();
  1464.  
  1465.         buildFromSorted(size, null, s, null);
  1466.     }
  1467.  
  1468.     /** Intended to be called only from TreeSet.readObject **/
  1469.     void readTreeSet(int size, java.io.ObjectInputStream s, Object defaultVal)
  1470.         throws java.io.IOException, ClassNotFoundException {
  1471.         buildFromSorted(size, null, s, defaultVal);
  1472.     }
  1473.  
  1474.     /** Intended to be called only from TreeSet.addAll **/
  1475.     void addAllForTreeSet(SortedSet set, Object defaultVal) {
  1476.       try {
  1477.           buildFromSorted(set.size(), set.iterator(), null, defaultVal);
  1478.       } catch (java.io.IOException cannotHappen) {
  1479.       } catch (ClassNotFoundException cannotHappen) {
  1480.       }
  1481.     }
  1482.  
  1483.  
  1484.     /**
  1485.      * Linear time tree building algorithm from sorted data.  Can accept keys
  1486.      * and/or values from iterator or stream. This leads to too many
  1487.      * parameters, but seems better than alternatives.  The four formats
  1488.      * that this method accepts are:
  1489.      *
  1490.      *      1) An iterator of Map.Entries.  (it != null, defaultVal == null).
  1491.      *    2) An iterator of keys.         (it != null, defaultVal != null).
  1492.      *      3) A stream of alternating serialized keys and values.
  1493.      *                      (it == null, defaultVal == null).
  1494.      *      4) A stream of serialized keys. (it == null, defaultVal != null).
  1495.      *
  1496.      * It is assumed that the comparator of the TreeMap is already set prior
  1497.      * to calling this method.
  1498.      *
  1499.      * @param size the number of keys (or key-value pairs) to be read from
  1500.      *          the iterator or stream.
  1501.      * @param it If non-null, new entries are created from entries
  1502.      *        or keys read from this iterator.
  1503.      * @param it If non-null, new entries are created from keys and
  1504.      *          possibly values read from this stream in serialized form.
  1505.      *        Exactly one of it and str should be non-null.
  1506.      * @param defaultVal if non-null, this default value is used for
  1507.      *        each value in the map.  If null, each value is read from
  1508.      *        iterator or stream, as described above.
  1509.      * @throws IOException propagated from stream reads. This cannot
  1510.      *         occur if str is null.
  1511.      * @throws ClassNotFoundException propagated from readObject. 
  1512.      *         This cannot occur if str is null.
  1513.      */
  1514.     private void buildFromSorted(int size, java.util.Iterator it,
  1515.                                   java.io.ObjectInputStream str,
  1516.                                   Object defaultVal)
  1517.         throws  java.io.IOException, ClassNotFoundException {
  1518.         this.size = size;
  1519.     root = buildFromSorted(0, 0, size-1, computeRedLevel(size),
  1520.                                it, str, defaultVal);
  1521.     }
  1522.  
  1523.     /**
  1524.      * Recursive "helper method" that does the real work of the
  1525.      * of the previous method.  Identically named parameters have
  1526.      * identical definitions.  Additional parameters are documented below.
  1527.      * It is assumed that the comparator and size fields of the TreeMap are
  1528.      * already set prior to calling this method.  (It ignores both fields.)
  1529.      *
  1530.      * @param level the current level of tree. Initial call should be 0.
  1531.      * @param lo the first element index of this subtree. Initial should be 0.
  1532.      * @param hi the last element index of this subtree.  Initial should be
  1533.      *          size-1.
  1534.      * @param redLevel the level at which nodes should be red. 
  1535.      *        Must be equal to computeRedLevel for tree of this size.
  1536.      */
  1537.     private static Entry buildFromSorted(int level, int lo, int hi,
  1538.                                          int redLevel,
  1539.                                          java.util.Iterator it, 
  1540.                                          java.io.ObjectInputStream str,
  1541.                                          Object defaultVal) 
  1542.         throws  java.io.IOException, ClassNotFoundException {
  1543.         /*
  1544.          * Strategy: The root is the middlemost element. To get to it, we
  1545.          * have to first recursively construct the entire left subtree,
  1546.          * so as to grab all of its elements. We can then proceed with right
  1547.          * subtree. 
  1548.          *
  1549.          * The lo and hi arguments are the minimum and maximum
  1550.          * indices to pull out of the iterator or stream for current subtree.
  1551.          * They are not actually indexed, we just proceed sequentially,
  1552.          * ensuring that items are extracted in corresponding order.
  1553.          */
  1554.  
  1555.         if (hi < lo) return null;
  1556.  
  1557.         int mid = (lo + hi) / 2;
  1558.         
  1559.         Entry left  = null;
  1560.         if (lo < mid) 
  1561.             left = buildFromSorted(level+1, lo, mid - 1, redLevel,
  1562.                                    it, str, defaultVal);
  1563.         
  1564.         // extract key and/or value from iterator or stream
  1565.         Object key;
  1566.         Object value;
  1567.         if (it != null) { // use iterator
  1568.             if (defaultVal==null) {
  1569.                 Map.Entry entry = (Map.Entry) it.next();
  1570.                 key = entry.getKey();
  1571.                 value = entry.getValue();
  1572.             } else {
  1573.                 key = it.next();
  1574.                 value = defaultVal;
  1575.             }
  1576.         } else { // use stream
  1577.             key = str.readObject();
  1578.             value = (defaultVal != null ? defaultVal : str.readObject());
  1579.         }
  1580.  
  1581.         Entry middle =  new Entry(key, value, null);
  1582.         
  1583.         // color nodes in non-full bottommost level red
  1584.         if (level == redLevel)
  1585.             middle.color = RED;
  1586.         
  1587.         if (left != null) { 
  1588.             middle.left = left; 
  1589.             left.parent = middle; 
  1590.         }
  1591.         
  1592.         if (mid < hi) {
  1593.             Entry right = buildFromSorted(level+1, mid+1, hi, redLevel,
  1594.                                           it, str, defaultVal);
  1595.             middle.right = right;
  1596.             right.parent = middle;
  1597.         }
  1598.         
  1599.         return middle;
  1600.     }
  1601.  
  1602.     /**
  1603.      * Find the level down to which to assign all nodes BLACK.  This is the
  1604.      * last `full' level of the complete binary tree produced by
  1605.      * buildTree. The remaining nodes are colored RED. (This makes a `nice'
  1606.      * set of color assignments wrt future insertions.) This level number is
  1607.      * computed by finding the number of splits needed to reach the zeroeth
  1608.      * node.  (The answer is ~lg(N), but in any case must be computed by same
  1609.      * quick O(lg(N)) loop.)
  1610.      */
  1611.     private static int computeRedLevel(int sz) {
  1612.         int level = 0;
  1613.         for (int m = sz - 1; m >= 0; m = m / 2 - 1) 
  1614.             level++;
  1615.         return level;
  1616.     }
  1617. }
  1618.